#include <logbase.h>
// O(N)
int myFind1(int *inbuf, int len, int findval)
{
    for (int i = 0; i < len; i++)
    {
        if (inbuf[i] == findval)
        {
            return i;
        }
    }
    return -1;
}

// O(log2(N))
int myFind2While(int *inbuf, int len, int findval)
{
    int idbeg = 0, idend = len - 1;
    int id2div = -1;
    while (1)
    {
        if (idbeg > idend)
        {
            return -1;
        }
        else if (idbeg == idend)
        {
            if (inbuf[idbeg] == findval)
            {
                return idbeg;
            }
            logdebugc("%d,%d", idbeg, inbuf[idbeg]);
            return -1;
        }
        else if (idbeg == idend - 1)
        {
            if (inbuf[idend] == findval)
            {
                return idend;
            }
            logdebugc("%d,%d", idend, inbuf[idend]);
            return -1;
        }
        else
        {
            id2div = (idbeg + idend) / 2;
            if (inbuf[id2div] == findval)
            {
                return id2div;
            }
            else if (inbuf[id2div] < findval)
            {
                idbeg = id2div;
            }
            else
            {
                idend = id2div;
            }
        }
    }
    return -1;
}

// O(log2(N))
int myFind2Call(int *inbuf, int idbeg, int idend, int findval)
{
    int id2div;
    if (idbeg > idend)
    {
        return -1;
    }
    else if (idbeg == idend)
    {
        logdebugc("%d,%d", idbeg, inbuf[idbeg]);
        if (inbuf[idbeg] == findval)
        {
            return idbeg;
        }
        return -1;
    }
    else if (idbeg == idend - 1)
    {
        logdebugc("%d,%d", idend, inbuf[idend]);
        if (inbuf[idend] == findval)
        {
            return idend;
        }
        return -1;
    }
    id2div = (idbeg + idend) / 2;
    if (inbuf[id2div] == findval)
    {
        return id2div;
    }
    else if (inbuf[id2div] < findval)
    {
        return myFind2Call(inbuf, id2div, idend, findval);
    }
    else
    {
        return myFind2Call(inbuf, idbeg, id2div, findval);
    }
}

// O(1)
int myFind3Hash(int *inbuf, int inlen, int findval)
{
    if (findval < inlen)
    {
        return findval;
    }
    return -1;
}

int main(int argc, char **argv)
{
    int chkbuf[16];
    int myfindVal = 15;
    for (int i = 0; i < ARRAY_LEN(chkbuf); i++)
    {
        chkbuf[i] = i;
    }
    logdebugc("find1nor :%d", myFind1(chkbuf, ARRAY_LEN(chkbuf), myfindVal));
    logdebugc("find2while :%d", myFind2While(chkbuf, ARRAY_LEN(chkbuf), myfindVal));
    logdebugc("find2call :%d", myFind2Call(chkbuf, 0, ARRAY_LEN(chkbuf), myfindVal));
    logdebugc("find3hash :%d", myFind3Hash(chkbuf, ARRAY_LEN(chkbuf), myfindVal));
    return 1;
}
